import java.util.Arrays;

/**
 * 一个机器人位于一个 m x n网格的左上角 （起始点在下图中标记为 “Start” ）。
 *
 * 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为 “Finish” ）。
 *
 * 问总共有多少条不同的路径？
 *

 * 链接：https://leetcode.cn/problems/unique-paths

 */
class UniquePaths {
    /**
     * 方法：动态规划
     * 状态：
     *
     *  子状态：从(0,0)到达(1,0),(1,1),(2,1),...(m-1,n-1)的路径数
     *
     *  F(i,j): 从(0,0)到达F(i,j)的路径数
     * 状态递推：
     *
     *  F(i,j) = F(i-1,j) + F(i,j-1)
     *
     * 初始化：
     *
     *  特殊情况：第0行和第0列
     *
     *  F(0,i) = 1
     *
     *  F(i,0) = 1
     *
     * 返回结果：
     *
     *  F(m-1,n-1)
     */
    /**
    public int uniquePaths(int m, int n) {
        int[][] dp=new int[m][n];
        for(int i=0;i<m;i++) {
            dp[i][0]=1;
        }
        for(int i=0;i<n;i++) {
            dp[0][i]=1;
        }
        for(int i=1;i<m;i++) {
            for(int j=1;j<n;j++) {
                dp[i][j]=dp[i][j-1]+dp[i-1][j];
            }
        }
        return dp[m-1][n-1];
    }
     */
    /**
     * 空间优化版
     */

        public int uniquePaths(int m, int n) {
            int[] dp=new int[n];
            Arrays.fill(dp,1);
            for(int i=1;i<m;i++) {
                for(int j=1;j<n;j++) {
                    dp[j]+=dp[j-1];
                }
            }
            return dp[n-1];
        }

}